iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 20
0

前言

昨天介紹了Binary tree的定義特性,今天講講儲存方式與走訪。

Binary Tree的儲存

  • 一維陣列

< Complete Binary tree >
https://ithelp.ithome.com.tw/upload/images/20181103/20112438g0pkpAD1T4.jpg

/ [1] [2] [3] [4] [5] [6]
tree[] A B C D E F

< Binary tree >
https://ithelp.ithome.com.tw/upload/images/20181104/20112438yIftieeCyH.jpg

/ [1] [2] [3] [4] [5] [6] [7]
tree[] A B - - C - D
  • 二維陣列
  • 鏈結

Binary Tree Traversal

圖形有走訪,tree也有走訪,按照順序,逐一走訪tree上的node。
簡單來說,就是 Tree中的所有節點都要走過一次

  • 以一個最簡單的Binary tree 來當示意圖:
    https://ithelp.ithome.com.tw/upload/images/20181103/20112438Gu7cBVjFX4.jpg
    那我們要走訪每一個點會有6種可能: ABC、ACB、BAC、BCA、CAB、CBA。
    但是,依照Binary tree的特性,都是由左向右,那就只會剩下3種方式:ABC、BAC、BCA。
    那又將這3種方式,分別命名為前序、中序、後序走訪。

  • 前序走訪 (preorder traverse)
    1.目前節點 / Root
    2.left subtree
    3.right subtree

    • 以下圖為例子:
      https://ithelp.ithome.com.tw/upload/images/20181103/20112438Gu7cBVjFX4.jpg
      => A -> B -> C
    • Hint: 前序走訪就是 root在前面
  • 中序走訪 (inorder traverse)
    1.left subtree
    2.目前節點 / Root
    3.right subtree

    • 以下圖為例子:
      https://ithelp.ithome.com.tw/upload/images/20181103/20112438Gu7cBVjFX4.jpg
      => B -> A -> C
    • Hint: 中序走訪就是 root在中間
  • 後序走訪 (postorder traverse)
    1.left subtree
    2.right subtree
    3.目前節點 / Root

    • 以下圖為例子:
      https://ithelp.ithome.com.tw/upload/images/20181103/20112438Gu7cBVjFX4.jpg
      => B -> C -> A
    • Hint: 後序走訪就是 root在後面

參考

細談資料結構 第六版
ISBN 978-986-312-014-8


上一篇
[Data Structure][Tree] - Binary Tree
下一篇
[Data Structure][Tree] - Binary Search Tree &Heap
系列文
學習資料結構30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言